package com.mj.HashMap;


import com.mj.printer.BinaryTreeInfo;
import com.mj.printer.BinaryTrees;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * @Author: LDeng
 * @Date: 2021-03-12 17:02
 */
public class HashMap<K, V> implements Map<K, V> {
    private static final boolean RED = false;
    private static final boolean BLACK = true;
    private static final int DEFAULT_CAPACITY = 1 << 4;//数组长度设计成2的n次方，方便位运算
    private int size;
    private static final float DEFAULT_LOAD_FACTOR=0.75f;//装填因子
    //hashmap里面存储了很多棵红黑树
    //使用table来存储每一棵红黑树的根节点
    private Node<K, V>[] table;//

    public HashMap() {
        table = new Node[DEFAULT_CAPACITY];
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        if (size == 0) return;
        size = 0;
        for (int i = 0; i < table.length; i++) {
            table[i] = null;//清空数组， 即清空红黑树
        }
    }

    @Override
    public V put(K key, V value) {
        resize();
        int index = index(key);
        //取出红黑树index位置的根节点
        Node<K, V> root = table[index];
        if (root == null) {//索引上没有根节点=>创建根节点
            root = createNode(key, value, null);
            table[index] = root;
            size++;
            //修复红黑树性质
            fixAfterPut(root);
            return null;//新节点=>返回空
        }
        //来到这里说明桶的红黑树上原来就有东西，哈希冲突
        //添加节点到红黑树上
        Node<K, V> parent = root;
        Node<K, V> node = root;
        int comp = 0;
        Node<K,V> result=null;
        boolean searched=false;//是否已经搜索过这个key
        while (node != null) {
            K k1 = key;
            K k2 = node.key;
            int h1 = index(key);
            int h2 = index(node);
            //comp = compare(k1, k2, h1, h2);//k1,k2,h1,h2
            parent = node;
            if(h1>h2){
                comp=1;
            }else if(h1<h2){
                comp=-1;
            }else if(Objects.equals(k1,k2)){//哈希值相等,key也equals
                comp=0;
            }else if(k1!=null&&k2!=null//哈希值相等，key是同一种类型，且key具有可比较性
                    &&k1.getClass()==k2.getClass()
                    &&k1 instanceof Comparable
                    &&(comp=((Comparable) k1).compareTo(k2))!=0){
                //什么也不做
            }else if(searched==false){//哈希值相等，key是同一种类型，且key不具备可比较性
                //扫描整棵树，查看是否有相同key的节点,
                //有就覆盖， 没有就根据内存地址决定向左向右
                if(node.left!=null&&(result=getNodeByKey(node.left,k1))!=null
                        ||node.right!=null&&(result=getNodeByKey(node.right,k1))!=null){
                    //存在这个key
                    comp=0;
                    node=result;
                }else {//不存在这个key,比唯一哈希值（内存地址）
                    //能来到这里表示所有的key都search过了
                    searched=true;
                    comp=System.identityHashCode(k1)-System.identityHashCode(k2);
                }
            }else{//searched 为true, 直接根据内存地址向左还是向右
                comp=System.identityHashCode(k1)-System.identityHashCode(k2);
            }
            if (comp > 0) {//element>node.element 传进来的元素大于节点元素
                node = node.right;
            } else if (comp < 0) {//
                node = node.left;
            } else {//相等, 覆盖值并返回
                node.key = key;//使用传进来的元素覆盖原来的元素
                V oldValue = node.value;
                node.value = value;
                return oldValue;
            }
        }
        // 插入到父节点的左边还是右边
        Node<K, V> newNode = createNode(key, value, parent);
        if (comp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;
        fixAfterPut(newNode);
        return null;
    }

    @Override
    public V get(K key) {
        Node<K, V> node = getNodeByKey(key);
        return node != null ? node.value : null;
    }

    //根据key查找节点
    private Node<K,V> getNodeByKey(K key){
        Node<K,V> root=table[index(key)];
        return root==null?null:getNodeByKey(root,key);
    }


    //在某个节点中根据key查找节点
    private Node<K, V> getNodeByKey(Node<K,V> node,K key) {
        //result 存储查找结果
        Node<K,V> result=null;
        //索引=>红黑树查找
        int comp=0;
        while (node != null) {
            K k1 = key;
            K k2 = node.key;
            int h1 = index(key);
            int h2 = index(node);
//            int comp = compare(k1,k2,h1,h2);//k1,k2,h1,h2
//            if (comp == 0) return node;
//            if (comp > 0) {//element>node.element 传进来的元素大于节点元素
//                node = node.right;
//            } else if (comp < 0) {//
//                node = node.left;
//            }
            //先比较哈希值
            if (h1 > h2) {
                node = node.right;
            } else if (h2 < h2) {
                node = node.left;
            } else if(Objects.equals(k1,k2)){
                return node;
            } else if (k1 != null && k2 != null//哈希值相等，key具有可比较性
                    && k1.getClass() == k2.getClass()
                    && k1 instanceof Comparable
                    && (comp = ((Comparable) k1).compareTo(k2))!=0) {
                if (comp > 0) {
                    node = node.right;
                } else if (comp < 0) {
                    node = node.left;
                } else {
                    return node;
                }
                //递归扫描右子树
            } else if(node.right!=null &&(result=getNodeByKey(node.right,key))!=null){//哈希值相等，key不具有可比较性，也不equals,或者k1,k2有一个空
                return result;
                //递归扫描左子树
            } else {//右边没找到，只能向左边找， 减少一次递归
                node=node.left;
            }
//            else if(node.left!=null&&(result=getNodeByKey(node.left,key))!=null){
//                return result;
//            } else {
//                //找不到
//                return null;
//            }
        }
        return null;
    }


    @Override
    public V remove(K key) {
        return remove(getNodeByKey(key));
    }

    protected V remove(Node<K, V> node) {
        if (node == null) return null;
        Node<K,V> willNode=node;
        size--;
        V oldValue = node.value;
        if (node.hasTwoChildren()) {//度为2, 使用被删除节点的前驱或者后继节点取代被删除的节点
            //找到后继节点
            Node<K, V> s = successor(node);
            //用后继节点的值覆盖node节点的值
            node.key = s.key;
            node.value = s.value;
            //删除后继节点
            node = s;//将node指向s节点， 为了下面统一删除度为1 和 0 的节点， 这里只做一个指向
        }
        //删除node节点（能执行到这里， node的度必然是1或者0）
        Node<K, V> replacement = node.left != null ? node.left : node.right;
        int index = index(node);
        if (replacement != null) {//node 度为1的节点
            //更改node的parent
            replacement.parent = node.parent;
            //更改parent的left,right
            if (node.parent == null) {//node 度为1，并且是根节点
                table[index] = replacement;
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else {//node == node.parent.right
                node.parent.right = replacement;
            }
            //删除节点后的处理（恢复平衡）,
            //这里不需要担心node被销毁， 因为他自生还有指针指向parent
            fixAfterRemove(node, replacement);

        } else if (node.parent == null) {//node度为0=>叶子节点,并且只有一个根节点
            table[index] = null;
            //删除节点后的处理（恢复平衡）
            fixAfterRemove(node, null);

        } else {//node是叶子节点，但不是根节点
            if (node == node.parent.left) {//node在父节点的左边
                node.parent.left = null;
            } else {//node在父节点的右边
                node.parent.right = null;
            }
            //删除节点后的处理（恢复平衡）
            fixAfterRemove(node, null);
        }
        //交给子类去实现
        afterRemove(willNode,node);
        return oldValue;
    }

    //后续节点， 中序遍历时的前一个节点（左子树的最后一个节点）
    protected Node<K, V> successor(Node<K, V> node) {
        if (node == null) return null;
        //1 ，右边不为空，前驱节点在右子树中(right.left.left.....)
        Node<K, V> p = node.right;
        if (p != null) {
            p = node.right;
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        //从父节点，祖父节点。。。中寻找前驱节点,
        // 父节点不为空， 并且本节点在父节点的左子树中
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

        //node.parent==null ==>返回空（node.parent）
        //node==node.parent.right ==> 本节点的parent节点就是前驱
        return node.parent;
    }


    @Override
    public boolean containsKey(K key) {
        return getNodeByKey(key) != null;
    }

    @Override
    public boolean containsValue(V value) {
        //遍历索引+遍历桶
        if (size == 0) return false;
        Queue<Node<K, V>> queue = new LinkedList<>();
        for (int i = 0; i < table.length; i++) {
            if (table[i] == null) continue;//根节点为空=>忽略
            queue.offer(table[i]);
            while (!queue.isEmpty()) {
                Node<K, V> node = queue.poll();
                if (Objects.equals(value, node.value)) return true;
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return false;
    }

    @Override
    public void traversal(Visitor<K, V> visitor) {
        //遍历索引+遍历桶
        if (size == 0 || visitor == null) return;
        Queue<Node<K, V>> queue = new LinkedList<>();
        for (int i = 0; i < table.length; i++) {
            if (table[i] == null) continue;//根节点为空=>忽略
            queue.offer(table[i]);
            while (!queue.isEmpty()) {
                Node<K, V> node = queue.poll();
                if (visitor.visit(node.key, node.value)) return;//visit方法返回true->找到了，停止遍历
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
    }


    private int hash(K key) {
        int hash = key == null ? 0 : key.hashCode();
        return hash ^ (hash >>> 16);
    }


    private int index(K key) {
        return hash(key) & (table.length - 1);
    }


    private int index(Node<K, V> node) {
        return index(node.key);
    }

    protected void fixAfterRemove(Node<K, V> node, Node<K, V> replacement) {
        //如果删除的是红色节点， 直接删除即可
        if (isRed(node)) return;

        //用以取代删除节点的节点是红色
        if (isRed(replacement)) {
            black(replacement);
            return;
        }
        Node<K, V> parent = node.parent;
        //删除的叶子节点是根节点， 直接返回
        if (parent == null) return;
        //能来到这里表示删除的是黑色叶子节点
        //Node<E> sibling=node.sibling();
        //判断被删除的节点是左边还是右边(用parent.left是否是空来判断)
        //如果parent.left是空， 则删除的节点在左边，那么sibling在必然在右边， 反之 sibling在左边
        //递归的情况，跟parent的连线还在，所有可以用isLeftChild()来判断
        boolean left = parent.left == null || node.isLeftChind();
        Node<K, V> sibling = left ? parent.right : parent.left;
        if (left) {//被删除的节点在左边，兄弟节点在右边
            if (isRed(sibling)) {//兄弟节点是红色=>转化成兄弟节点是黑色，复用
                black(sibling);
                red(parent);
                rotateLeft(parent);
                //更换兄弟
                sibling = parent.right;//sibling指向parent.left（黑色）
            }
            //现在可以统一处理sibling是黑色的情况
            if (isBlack(sibling.left) && isBlack(sibling.right)) {//黑黑，没有红色子节点可以借出
                //判断父节点颜色
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentBlack) {
                    fixAfterRemove(parent, null);
                }
            } else {//VS 黑红+红黑+红红, 兄弟节点至少有一个红色节点可以借出
                //向兄弟节点借元素， 三种情况
                //    红节点在兄弟节点右边 兄弟节点左旋+父节点右旋，
                //    红节点在兄弟节点左边             父节点右旋
                //    红节点两边走有，                 父节点右旋
                //这里先把第一种特殊处理一下， 然后统一代码左父节点右旋
                if (isBlack(sibling.right)) {//红节点在右边，先旋转兄弟节点,在将sibling指向父节点的左边
                    rotateRight(sibling);
                    sibling = parent.right;//sibling指向
                }
                //拿到被删除节点父节点的颜色，给兄弟染色
                color(sibling, colorOf(parent));
                black(sibling.right);
                black(parent);
                rotateLeft(parent);
            }

        } else {//被删除的节点在右边，兄弟节点在左边（对称处理）
            if (isRed(sibling)) {//兄弟节点是红色=>转化成兄弟节点是黑色，复用
                black(sibling);
                red(parent);
                rotateRight(parent);
                //更换兄弟
                sibling = parent.left;//sibling指向parent.left（黑色）
            }
            //现在可以统一处理sibling是黑色的情况
            if (isBlack(sibling.left) && isBlack(sibling.right)) {//黑黑，没有红色子节点可以借出
                //判断父节点颜色
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentBlack) {
                    fixAfterRemove(parent, null);
                }
            } else {//VS 黑红+红黑+红红, 兄弟节点至少有一个红色节点可以借出
                //向兄弟节点借元素， 三种情况
                //    红节点在兄弟节点右边 兄弟节点左旋+父节点右旋，
                //    红节点在兄弟节点左边             父节点右旋
                //    红节点两边走有，                 父节点右旋
                //这里先把第一种特殊处理一下， 然后统一代码左父节点右旋
                if (isBlack(sibling.left)) {//红节点在右边，先旋转兄弟节点,在将sibling指向父节点的左边
                    rotateLeft(sibling);
                    sibling = parent.left;//sibling指向
                }
                //拿到被删除节点父节点的颜色，给兄弟染色
                color(sibling, colorOf(parent));
                black(sibling.left);
                black(parent);
                rotateRight(parent);
            }
        }
    }

    private void fixAfterPut(Node<K, V> node) {
        Node<K, V> parent = node.parent;
        //如果添加的是根节点, 或者上溢到根节点（递归退出条件）
        if (parent == null) {
            black(node);
            return;
        }
        //如果父节点是黑色，直接返回
        if (isBlack(parent)) return;
        Node<K, V> uncle = parent.sibling();
        Node<K, V> grand = parent.parent;
        //叔父节点是红色
        if (isRed(uncle)) {
            black(parent);
            black(uncle);
            Node<K, V> grand_red = red(grand);//祖父节点染成红色，上溢并递归
            fixAfterPut(grand_red);
            return;
        }
        //叔父节点不是红色
        if (parent.isLeftChind()) {//L
            red(grand);
            if (node.isLeftChind()) {//LL
                black(parent);
            } else {//LR
                black(node);
                rotateLeft(parent);
            }
            rotateRight(grand);
        } else {//R
            red(grand);
            if (node.isLeftChind()) {//RL
                black(node);
                rotateRight(parent);
            } else {//RR
                black(parent);
            }
            rotateLeft(grand);
        }
    }

    //节点染色并返回染色后的节点
    private Node<K, V> color(Node<K, V> node, boolean color) {
        if (node == null) return node;
        node.color = color;
        return node;
    }

    //将节点染成红色并返回
    private Node<K, V> red(Node<K, V> node) {
        return color(node, RED);
    }

    //将节点染成黑色并返回
    private Node<K, V> black(Node<K, V> node) {
        return color(node, BLACK);
    }

    //取出当前节点颜色
    private boolean colorOf(Node<K, V> node) {
        //空节点返回黑色，其他根据实际是什么颜色就返回什么颜色
        return node == null ? BLACK : node.color;
    }

    //判断节点是否为黑色
    private boolean isBlack(Node<K, V> node) {
        return colorOf(node) == BLACK;
    }

    //判断节点是否为红色
    private boolean isRed(Node<K, V> node) {
        return colorOf(node) == RED;
    }


    private void rotateLeft(Node<K, V> grand) {//节点左旋转
        Node<K, V> p = grand.right;
        Node<K, V> child = p.left;
        //更新g的右节点和p的左节点
        grand.right = child;
        p.left = grand;

        afterRotate(grand, p, child);
    }

    private void rotateRight(Node<K, V> grand) {
        Node<K, V> p = grand.left;
        Node<K, V> child = p.right;
        grand.left = child;
        p.right = grand;
        afterRotate(grand, p, child);
    }

    private void afterRotate(Node<K, V> grand, Node<K, V> p, Node<K, V> child) {
        //更新p,g 的parent属性( 双向 )
        p.parent = grand.parent;
        if (grand.isLeftChind()) {//g是父节点的左节点
            grand.parent.left = p;
        } else if (grand.isRightChild()) {//g是父节点的右节点
            grand.parent.right = p;
        } else {//父节点是空，g是根节点
            table[index(grand)] = p;//根节点指向p
        }
        //更新p左子节点的parent
        if (child != null) {
            child.parent = grand;
        }
        //更新g的parent
        grand.parent = p;
    }

    /**
     * @param k1
     * @param k2
     * @param h1 k1的hashCode
     * @param h2 k2的hashCode
     * @return
     */
//    private int compare(K k1, K k2, int h1, int h2) {
//        //比较哈希值
//        int result = h1 - h2;
//        if (result != 0) return result;
//        //比较equals
//        if (Objects.equals(k1, k2)) return 0;//=> key是equals的， 返回0， 覆盖/找到元素
//        //能来到到这里表示哈希值相等，但是key不equals，=>添加，或者去左右子树查找
//        //先比较类名决定放在左边还是右边
//        if (k1 != null && k2 != null
//                && k1.getClass() == k2.getClass()
//                && k1 instanceof Comparable) {
//            if (k1 instanceof Comparable) {//k1和k2的类是实现了comparable接口,具有可比较性
//                return ((Comparable) k1).compareTo(k2);
//            }
//        }
//        //来到这里剩下两种情况：
//        //1，key是同一种类型，但不具备可比较性
//        //2，k1,k2有一个为空
//        //==>只能比较内存地址
//        return System.identityHashCode(k1) - System.identityHashCode(k2);
//    }

    //扩容
        private void resize(){
          //装填因子<=0.75
          if(size/table.length<=DEFAULT_LOAD_FACTOR) return;
          Node<K,V>[] oldTable=table;
          table=new Node[oldTable.length<<1];//申请新的内存空间 2倍
            //遍历整个桶和红黑树，取出节点 搬到新的数组中，
            Queue<Node<K, V>> queue = new LinkedList<>();
            for (int i = 0; i < oldTable.length; i++) {
                if (oldTable[i] == null) continue;//根节点为空=>忽略
                queue.offer(oldTable[i]);
                while (!queue.isEmpty()) {
                    Node<K, V> node = queue.poll();
                    if (node.left != null) {
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        queue.offer(node.right);
                    }
                    moveNode(node);
                }
            }
        }
        //移动节点的方法
        private void moveNode(Node<K,V> newNode){
            //重置
            newNode.parent=null;
            newNode.left=null;
            newNode.right=null;
            newNode.color=RED;
            int index = index(newNode);
            //取出红黑树index位置的根节点
            Node<K, V> root = table[index];
            if (root == null) {//索引上没有根节点=>创建根节点
                root = newNode;
                table[index] = root;
                //修复红黑树性质
                fixAfterPut(root);
                return ;//新节点=>返回空
            }
            //来到这里说明桶的红黑树上原来就有东西，哈希冲突
            //添加节点到红黑树上
            Node<K, V> parent = root;
            Node<K, V> node = root;
            int comp = 0;
            while (node != null) {
                K k1 = newNode.key;
                K k2 = node.key;
                int h1 = index(newNode);
                int h2 = index(node);
                //comp = compare(k1, k2, h1, h2);//k1,k2,h1,h2
                parent = node;
                if(h1>h2){
                    comp=1;
                }else if(h1<h2){
                    comp=-1;
                }else if(k1!=null&&k2!=null//哈希值相等，key是同一种类型，且key具有可比较性
                        &&k1.getClass()==k2.getClass()
                        &&k1 instanceof Comparable
                        &&(comp=((Comparable) k1).compareTo(k2))!=0){
                    //什么也不做
                }else{//searched 为true, 直接根据内存地址向左还是向右
                    comp=System.identityHashCode(k1)-System.identityHashCode(k2);
                }
                if (comp > 0) {//element>node.element 传进来的元素大于节点元素
                    node = node.right;
                } else if (comp < 0) {//
                    node = node.left;
                }
            }
            // 插入到父节点的左边还是右边
            newNode.parent=parent;
            if (comp > 0) {
                parent.right = newNode;
            } else {
                parent.left = newNode;
            }
            fixAfterPut(newNode);
        }

        protected Node<K,V> createNode(K key, V value, Node<K, V> parent){

            return new Node<K,V>(key,value,parent);

        }



        protected void afterRemove(Node<K,V> willNode,Node<K,V> removedNode){

        };

    protected static class Node<K, V> {
        int nodeHash;
        K key;
        V value;
        boolean color = RED;
        Node<K, V> left;
        Node<K, V> right;
        Node<K, V> parent;

        public Node(K key, V value, Node<K, V> parent) {//构造
            this.key = key;
            this.value = value;
            this.parent = parent;
            //创建节点的时候就计算好keyhash，存储起来， 避免以后一直调用计算hashcode的方法
            int keyHash = key == null ? 0 : key.hashCode();
            this.nodeHash = keyHash ^ (keyHash >>> 16);
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        public boolean isLeftChind() {
            return parent != null && this == parent.left;
        }

        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }

        public Node<K, V> sibling() {
            if (isLeftChind()) {
                return parent.right;
            }
            if (isRightChild()) {
                return parent.left;
            }
            //没有左也没有右，父节点为空， 返回空兄弟节点
            return null;
        }

        @Override
        public String toString() {
            return "Node_" + key + "_" + value;
        }
    }

    public void print() {
        if (size == 0) return;

        for (int i = 0; i < table.length; i++) {
            final Node<K, V> root = table[i];

            System.out.println("\n" + "【index】：" + i);

            BinaryTrees.print(new BinaryTreeInfo() {
                @Override
                public Object root() {
                    return root;
                }

                @Override
                public Object left(Object node) {
                    return ((Node<K, V>) node).left;
                }

                @Override
                public Object right(Object node) {
                    return ((Node<K, V>) node).right;
                }

                @Override
                public Object string(Object node) {
                    return node;
                }
            });
            System.out.println("\n====================");
        }
    }
}
